/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class MedianOfTwoSortedArrays {

	public int getLowRank(int A[], int val) {
		int n = A.length;
		int l = 0, r = n - 1, mid;
		while (l <= r) {
			mid = l + r >> 1;
			if (A[mid] >= val) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return r + 1;
	}

	public int getHighRank(int A[], int val) {
		int n = A.length;
		int l = 0, r = n - 1, mid;
		while (l <= r) {
			mid = l + r >> 1;
			if (A[mid] > val) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return r + 1;
	}

	public int find(int A[], int B[], int k) {
		int n = A.length, m = B.length;
		int l, r, mid;
		l = 0;
		r = n - 1;
		while (l <= r) {
			mid = l + r >> 1;
			int hrank = getHighRank(B, A[mid]);
			int lrank = getLowRank(B, A[mid]);
			if (lrank + mid <= k && k <= hrank + mid)
				return A[mid];
			if (lrank + mid > k)
				r = mid - 1;
			else
				l = mid + 1;
		}
		l = 0;
		r = m - 1;
		while (l <= r) {
			mid = l + r >> 1;
			int hrank = getHighRank(A, B[mid]);
			int lrank = getLowRank(A, B[mid]);
			if (lrank + mid <= k && k <= hrank + mid)
				return B[mid];
			if (lrank + mid > k)
				r = mid - 1;
			else
				l = mid + 1;
		}
		return 0;
	}

	public double findMedianSortedArrays(int A[], int B[]) {
		int n = A.length, m = B.length;
		if (m + n == 0)
			return 0.0;
		return (find(A, B, (m + n - 1) / 2) + find(A, B, (m + n) / 2)) * 0.5;
	}

	public static void main(String[] args) {
		MedianOfTwoSortedArrays a = new MedianOfTwoSortedArrays();
		System.out.println(a.findMedianSortedArrays(new int[] { 1, 5 },
				new int[] { 2, 3, 4, 8 }));
	}

}
